package Algorithm.krusKal;

import java.util.Arrays;


/**
 * 克鲁斯卡尔算法（公交站问题）
 */
public class KruskalCase {

    private int edgeNum;  //边的个数
    private char[] vertexs;  //顶点的数组
    private int[][] matrix;  //邻接矩阵

    //使用INF这个表示两个顶点不能连通
    private static final int INF = Integer.MAX_VALUE;
    public static void main(String[] args) {
        char[] vertexs = {'A','B','C','D','E','F','G'};
        int[][] matrix = {
                {0,12,INF,INF,INF,16,14},
                {12,0,10,INF,INF,7,INF},
                {INF,10,0,3,5,6,INF},
                {INF,INF,3,0,4,INF,INF},
                {INF,INF,5,4,0,2,8},
                {16,7,6,INF,2,0,9},
                {14,INF,INF,INF,8,9,0}
        };
        KruskalCase kruskalCase = new KruskalCase(vertexs, matrix);
        kruskalCase.print();

        EData[] edges = kruskalCase.getEdges();
        System.out.println(Arrays.toString(edges));
        kruskalCase.sortEdge(edges);
        System.out.println(Arrays.toString(edges));
        kruskalCase.kruskal();



    }

    //构造器
    public KruskalCase(char[] vertexs, int[][] matrix){
        //初始化顶点数和边的个数
        int vlen = vertexs.length;

        //初始化顶点
        this.vertexs = new char[vlen];
        for (int i = 0; i <vertexs.length ; i++) {
            this.vertexs[i] = vertexs[i];
        }

        //初始化边
        this.matrix = new int[vlen][vlen];
        for (int i = 0; i <vlen ; i++) {
            for (int j = 0; j <vlen ; j++) {
                this.matrix[i][j] = matrix[i][j];
            }
        }

        //统计边
        for (int i = 0; i <vlen ; i++) {
            for (int j = i+1; j <vlen ; j++) {
                if(this.matrix[i][j] != INF){  //说明连通
                    edgeNum++;  //将边的数量加加
                }
            }
        }

    }


    //克鲁斯卡尔核心算法
    public void kruskal(){
        int index = 0; //表示最后数组的索引
        int[] ends = new int[edgeNum];  //用于保存已有最小生成树，用于判断是否构成回路
        //创建结果数组，保存最后的最小生成树
        EData[] rets = new EData[edgeNum];

        //获取原始图中所有的边的集合,一共有12条边
        EData[] edges = getEdges();
        System.out.println("边："+Arrays.toString(edges)+" 条数:"+edges.length);

        //按照边的权值大小进行排序(从小到大)
        sortEdge(edges);

        //遍历edges数组，将边添加到最小生成树，判断准备加入的边是否构成了回路。
        for (int i = 0; i <edgeNum ; i++) {
            //获取到第i条边的第一个顶点，（起点）
            int p1 = getPosition(edges[i].start);
            //获取到第i条边的第二个顶点，（终点）
            int p2 = getPosition(edges[i].end);

            //获取p1这个顶点在已有的最小生成树的终点是哪个
            int m = getEnd(ends,p1);
            //获取p2这个顶点在已有的最小生成树的终点是哪个
            int n = getEnd(ends,p2);

            //判断是否构成回路
            if(m !=n){
                //没有构成回路
                ends[m] = n; //设置m在已有最小生成树的终点
                rets[index++] = edges[i];  //有一条边加入到rets数组

            }
        }

        //统计并且打印最小生成树
        System.out.println("最小生成树为=" + Arrays.toString(rets));


    }


    //打印邻接矩阵
    public void print() {
        System.out.println("邻接矩阵为：");
        for (int i = 0; i < vertexs.length; i++) {
            for (int j = 0; j < vertexs.length; j++) {
                System.out.printf("%12d\t", matrix[i][j]);
            }
            System.out.println("\n");
        }
    }

    //对边的权值进行排序处理（冒泡排序）
    private void sortEdge(EData[] edges) {
        for (int i = 0; i < edges.length - 1; i++) {
            for (int j = 0; j < edges.length - 1 - i; j++) {
                if (edges[j].weight > edges[j + 1].weight) { //进行交换
                    EData tmp = edges[j];
                    edges[j] = edges[j + 1];
                    edges[j + 1] = tmp;
                }
            }
        }
    }

    /**
     *
     * @param ch 传入顶点的值，
     * @return 返回顶点对应的下标
     */
    private int getPosition(char ch){
        for (int i = 0; i <vertexs.length ; i++) {
            if(vertexs[i] == ch){ //找到
                return i;
            }
        }
        return -1;  //找不到
    }

    //获取图中的边，放到Edata[] 数组中，后面需要遍历
    //通过邻接矩阵获取 [['A','B',12],[ ]  ]
    private EData[] getEdges(){
        int index = 0;
        EData[] edges = new EData[edgeNum];
        for (int i = 0; i <vertexs.length ; i++) {
            for (int j = i+1; j <vertexs.length ; j++) {
                if(matrix[i][j] !=INF){  //说明连通
                    edges[index++] = new EData(vertexs[i],vertexs[j],matrix[i][j]);
                }
            }
        }
        return edges;

    }

    /**
     *  获取下标为i的顶点的终点，用于判断两个顶点的终点是否相同
     * @param ends 记录各个顶点对应的终点是哪个，ends数组在遍历过程中，逐步形成
     * @param i 表示传入的顶点对应的下标
     * @return  下标为i的这个顶点对应的终点下标
     */
    private int getEnd(int[] ends, int i){

        while (ends[i] !=0){
            i=ends[i];
        }
        return i;
    }
}

//创建一个类，它的对象实例就表示一条边
class EData{
    char start; //边的一个点
    char end ; //边的另外一个点
    int weight; //边的权值

    //构造器
    public EData(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return "EData{" +
                "start=" + start +
                ", end=" + end +
                ", weight=" + weight +
                '}';
    }
}
